#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+10,INF=0x7fffffff;
int n,a[MAXN],f[MAXN],head[MAXN*2],cnt,idx[MAXN*2];
struct edge
{
	int v,next,val;
}e[MAXN*20];
void addedge(int x,int y,int z)
{
	e[cnt]=(edge){y,head[x],z};
	head[x]=cnt++;
	return;
}
void bfs()
{
	memset(idx,0,sizeof(idx));
	queue<int>q;
	q.push(0);
	idx[0]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			if(idx[v]||!e[i].val)continue;
			idx[v]=idx[u]+1;
			q.push(v);
		}
	}
	return;
}
int dfs(int u,int _min)
{
	if(u==n*2+1)return _min;
	int ret=0,k;
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		if(idx[v]!=idx[u]+1||!e[i].val)continue;
		k=dfs(v,min(_min-ret,e[i].val));
		e[i].val-=k;
		e[i^1].val+=k;
		ret+=k;
		if(ret==_min)break;
	}
	return ret;
}
int dinic()
{
	int ret=0;
	while(true)
	{
		bfs();
		if(!idx[n*2+1])break;
		ret+=dfs(0,INF);
		if(ret==INF)break;
	}
	return ret;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)
	{
		f[i]=1;
		for(int j=1;j<i;++j)
			if(a[j]<=a[i])f[i]=max(f[i],f[j]+1);
	}
	int ans=0;
	for(int i=1;i<=n;++i)ans=max(ans,f[i]);
	printf("%d\n",ans);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;++i)
	{
		addedge(i,i+n,1);
		addedge(i+n,i,0);
		if(f[i]==1)
		{
			addedge(0,i,1);
			addedge(i,0,0);
		}
		if(f[i]==ans)
		{
			addedge(i+n,n*2+1,1);
			addedge(n*2+1,i+n,0);
		}
		for(int j=1;j<i;++j)
		{
			if(a[j]<=a[i]&&f[j]+1==f[i])
			{
				addedge(j+n,i,1);
				addedge(i,j+n,0);
			}
		}
	}
	printf("%d\n",dinic());
	cnt=0;memset(head,-1,sizeof(head));
	for(int i=1;i<=n;++i)
	{
		int v=(i==1||i==n)?INF:1;
		addedge(i,i+n,v);
		addedge(i+n,i,0);
		if(f[i]==1)
		{
			addedge(0,i,v);
			addedge(i,0,0);
		}
		if(f[i]==ans)
		{
			addedge(i+n,n*2+1,v);
			addedge(n*2+1,i+n,0);
		}
		for(int j=1;j<i;++j)
		{
			if(a[j]<=a[i]&&f[j]+1==f[i])
			{
				addedge(j+n,i,1);
				addedge(i,j+n,0);
			}
		}
	}
	ans=dinic();
	printf("%d\n",ans==INF?n:ans);
	return 0;
}
